Systems for replicating resources are becoming increasingly important to ensure availability and fault tolerance in large networks. Corporate networks that replicate files containing domain credentials and policies are one example where availability, scalability, consistency, and reliability are critical. These requirements do not necessarily interact in a cooperative manner.
Version vectors have been used when replicating resources. A version vector may be viewed as a global set of counters or clocks of machines participating in a replica set. Each machine participating in the replica set maintains a version vector that represents the machine's current latest version and the latest versions that the machine has received with respect to other machines. Each time a resource is created, modified, or deleted from a machine, the resource's version is set to a version number equivalent to the current version number for that machine plus one. The version vector for that machine is also updated to reflect that the version number for that machine has been incremented.
During synchronization, a version vector may be transmitted for use in synchronizing files. For example, if machines A and B engage in a synchronization activity such as a join, machine B may transmit its version vector to A. Upon receiving B's version vector, A may then transmit changes for all resources, if any, that have versions not subsumed by B's version vector.
Version vectors have shortcomings when the growth of knowledge on a machine is not monotonic or sequential. For example, when version vectors are used in file replication systems, some objects may need one or more other objects to be created before they can be created. For example, both a directory and files in that directory may be new and need to be transmitted during synchronization. If a file is transmitted before its parent directory, an error may occur when creating the file. Version vectors do not adequately address this and other problems.